翻訳と辞書 Words near each other ・ Random Passage ・ Random password generator ・ Random permutation ・ Random permutation statistics ・ Random phase approximation ・ Random phase multiple access ・ Random plot generator ・ Random positioning machine ・ Random projection ・ Random Quest ・ Random Recipe ・ Random regular graph ・ Random Roads Collection ・ Random search ・ Random seed ・ Random self-reducibility ・ Random sequence ・ Random Shoes ・ Random Spirit Lover ・ Random stimulus ・ Random structure function ・ Random subspace method ・ Random test generator ・ Random testing ・ Random Thoughts ・ Random Thoughts (Don Pullen album) ・ Random Thoughts (Faye Wong album) ・ Random Thoughts (Koolism album) ・ Random tree ・ Random variable Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Random self-reducibility ： ウィキペディア英語版 Random self-reducibility Random self-reducibility (RSR) is the rule that a good algorithm for the average case implies a good algorithm for the worst case. RSR is the ability to solve all instances of a problem by solving a large fraction of the instances. ==Definition== If a function ''f'' evaluating any instance ''x'' can be reduced in polynomial time to the evaluation of ''f'' on one or more random instances ''yi'', then it is self-reducible (this is also known as a ''non-adaptive uniform self-reduction''). In a random self-reduction, an arbitrary worst-case instance ''x'' in the domain of ''f'' is mapped to a random set of instances ''y''1, ..., ''yk''. This is done so that ''f''(''x'') can be computed in polynomial time, given the coin-toss sequence from the mapping, ''x'', and ''f''(''y''1), ..., ''f''(''yk''). Therefore, taking the average with respect to the induced distribution on ''yi'', the average-case complexity of ''f'' is the same (within polynomial factors) as the worst-case randomized complexity of ''f''. One special case of note is when each random instance ''yi'' is distributed uniformly over the entire set of elements in the domain of ''f'' that have a length of |''x''|. In this case ''f'' is as hard on average as it is in the worst case. This approach contains two key restrictions. First the generation of ''y''1, ..., ''yk'' is performed non-adaptively. This means that ''y''2 is picked before ''f''(''y''1) is known. Second, it is not necessary that the points ''y''1, ..., ''yk'' be uniformly distributed. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Random self-reducibility」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.